987 661
611691720 97150759 138008408 740986461 989698509 116173157 733351314 833111489 9828988 166362782 34542622 157899336 482184283 597180639 805759804 972286027 646922754 818399084 715311999 140781718 640339361 921659708 116369999 119696618 347535223 940829560 655994471 856013948 519046748 362809856 855558744 144491636 786002488 225242086 352702213 92512879 428487305 643172336 83055141 931525886 83394274 52657946 499991749 484922917 422183782 129789714 748499907 264249309 784597841 344263867 877295188 159888530 989149551 577474730 147592830 578647973 302507683 112578476 686496671 275401195 324074594 98200894 694028516 659812908 297748277 173053971 725063635 781084581 262396219 571222162 905846978 39401094 749792932 624701270 724647261 346723445 225918007 17403820 421009188 9445130 845624269 93053464 759938026 221602897 489644755 221042896 400597591 618517835 590655180 235251263 954911335 945469036 881400781 829199236 106450921 590428190 481950976 666609392 938738946 935237949 437019937 98842764 757604519 877285786 701367556 251032721 940119334 642855033 568272397 254871533 828116638 877570834 574811830 122242757 385380737 792305939 951499021 159607533 354593561 449799452 397543731 717452402 511915009 293003073 559087582 32034833 290970792 602678156 473618135 306703293 880639954 872018553 415407485 534166813 843471126 780567417 349150017 150730251 377107808 340836719 857569320 926924054 162483569 816717110 156791116 374326785 560237658 154989592 199568731 902470722 506629125 858789976 186400534 850756996 447845804 906244010 111101396 977385509 751063136 643141046 619766780 672931768 60737923 351745176 733393806 533238661 976847182 109594467 163537051 711751940 953736012 412534425 643617225 727951974 758255837 406317748 329304272 238363916 851433908 450259617 873111295 259340301 671224410 855306304 949164471 449380533 141598889 509680357 563076847 709174016 19742289 633998298 999901103 727207459 10769238 969579227 428670101 413628676 921952399 304579224 117126227 501022397 961759273 694608694 625970222 563741469 730166819 393600207 319020161 228123430 331845840 78583277 693815096 120496016 64251736 42271251 466574422 676630341 888223286 624291892 585586799 483757539 546183611 736359226 963678510 937370685 359353994 284646528 632266704 729876186 38267930 840465497 10328488 367641717 479513399 301239431 157493401 966697083 82957954 343008964 110593439 348696464 75276012 12158780 300282182 139045898 759223871 762366737 73839153 803573364 943847317 327209174 104521109 155777549 814935007 940185365 253372347 789777734 789891167 957309641 362499713 298161736 527582510 490320356 53403098 548488044 209372599 68483019 512325705 127225280 489680698 478167509 247799658 114800009 177478986 566558159 526602346 760870587 494901839 648108154 670947466 61713795 658856965 341604364 125092255 736347326 291284475 676809387 208913045 940025471 586613781 192838901 435522023 418036877 978399499 131965051 642805801 535205090 470088424 507223617 318648959 892866605 240829835 590117696 545798435 56586833 851615017 608042725 876478435 912904932 206898377 754321807 687789216 596593073 826207431 596899604 895997392 823203638 336501585 859595069 751151868 19000615 286972653 414392389 35098947 255328489 413531889 945089374 103510997 121058840 578993162 377691436 776942714 176605953 473381046 48606791 683779593 278176040 263381449 54339518 731004145 197888452 824741612 157040015 134248371 904376894 520253209 393973040 184159589 694601910 458716449 971911689 223532081 883639422 337651750 371049463 957909460 228674717 54161441 579127243 539787807 282988109 264948317 392635849 189156729 834881405 694795770 232477738 146803548 144838479 517393515 318178202 828814548 687200923 749251576 690976186 481858307 406134891 776178237 219664287 944471455 430324861 111556777 641376337 593498482 728488388 77183232 330816333 873291481 854328039 362295770 724285188 512132166 966632641 929424673 41621850 735268031 565794015 291963031 890150439 923001436 929511941 481771598 7518649 698922188 870353577 579694894 699669329 567164369 755153782 346866546 452207009 538184127 648851915 476215595 404241236 873559041 236428858 556768956 19334534 853853589 811497737 494797148 584929352 833815947 520660660 240826263 198687006 328165769 407796329 749692877 828828032 416795722 421039754 238814386 217838428 159562266 308625711 405266892 736807826 483923292 460037793 703525881 199835255 523774212 194201568 455020518 89222739 501057310 909889823 858533016 486286819 824746309 451515458 936393191 200835799 293008172 651122023 910189822 482345557 269972249 987096410 456131805 515718516 884271717 991295519 731223255 305281986 398202877 804207980 247823124 511306175 167397604 261930796 457808144 473520992 834662575 918289917 673153562 961208973 435646983 386378675 555098582 220962210 519402283 274749395 918441660 559332850 383046763 119110680 984516246 583341119 257289902 992245490 399105286 868163396 352423405 701471746 586689534 136152619 772889013 398514336 658872902 529882903 840338345 59496533 616730105 668854684 20816894 732649313 931993864 20735810 434510334 96293686 68510645 598052357 794127493 199029499 930817818 418501336 941094023 802684426 658621344 169396253 907361160 565259890 583175048 784063022 509779490 721411445 464013669 215900120 679244931 842317835 156285600 510948571 852463852 638966622 959604723 203075179 565669427 290751820 251507695 307981746 968457282 76504808 170483062 362611787 308456086 30536442 777928257 797749961 312574656 188431994 618175323 267192110 287859943 627971864 365624227 746110836 140268613 19806135 758694479 389348360 551269286 972495598 511253860 191989833 567252972 434314630 98916927 759222542 27684493 174407935 538724367 666536221 622786067 2967562 945431640 176776629 589963419 148317456 388578161 401494277 384833623 777180842 891336455 318367410 358698508 271645222 923222680 593846357 888203157 298146825 712826873 579199483 282120798 778124424 511599569 539487395 370748905 809581069 486972443 91605700 858338892 881601464 98937512 912714436 118823601 906394075 105714074 448512897 194595286 211396733 908136427 385117388 146576523 522224600 942012388 900767210 371657782 718449884 178765734 677153810 552945490 576368042 196006308 851137777 811835371 902867993 512071975 426138920 82896931 361667636 505393353 529658573 717533361 412409529 870014714 374267366 759087965 699285404 789856895 329070833 296025477 65336962 673209069 208296287 651618460 599907143 15912242 564789780 592098469 322719352 766776845 843448297 484496572 727277529 781200529 317140011 216993165 30140641 32847526 40228121 172443611 947477817 349137288 874404969 892051707 232736577 768792646 844563395 284022614 339325579 263759940 872851780 642014955 886528606 237526970 90932221 883835850 841824820 144935986 979763826 188490906 570082876 115814670 380560156 491310356 101983193 674778111 801058023 493367941 520174625 495722383 782499765 387926608 454016094 524552088 147573976 561264234 658657937 979613643 277066652 132151772 514307562 636963883 797753787 872902981 833567057 339087759 211152359 999932245 426463713 372103203 649172035 434100563 290224487 424719847 279306474 117771672 3451623 456742703 141450343 741110290 890700055 222133537 711680059 676987586 413956835 462528570 431712603 679879230 726762983 567068361 523498159 657172016 549104888 915174259 450993556 787996629 874867356 579242925 401980507 95242366 505446796 796612677 408347848 376865810 960639289 793742810 267372691 495658379 647572549 717300575 128031211 142329204 494682373 898484892 285583342 943004274 999914502 978897581 449976113 959223224 927692933 817872001 363951678 993105297 15282421 937068380 105159697 464610778 427990909 489874773 894084251 900865156 555902072 783708121 924565824 880796183 884128499 866040358 985405784 507140138 197144882 116163025 8472241 985988076 320070443 15866177 522209291 269027486 317312777 506137137 916341147 555060247 916196778 249496626 559604105 85496127 724546338 134864678 892402289 903777940 219511606 307999686 387247078 970077352 662034402 264034846 774128875 280787104 28263380 374894092 706346616 707036855 982644462 529214404 520367611 40488633 472601799 149484622 324758996 515013256 451994411 98514950 455552471 693033627 660759703 402783004 247707598 7300218 546843838 672706066 17020405 34809155 85517062 413227585 448440188 194978344 635791116 799787604 837017353 24496879 717499676 159121098 671810355 603928176 970376377 447970936 378453768 448405787 105711899 832550149 763855496 800575855 602803116 383891309 118142247 592706692 447120010 553212031 735483983 35270786 119389961 167446367 644462556 996127528 606416430 916470788 957208734 887462470 350267188 647845819 85921498 546813507 146929163 525285282 386290377 319077015 334562260 260928814 189970200 139741778 93752678 12563622 567365991 338441364 400947149 455269797 814996170 381946643 879660741 946101660 594124363 155373208 499961155 320564813 732468581 44312962 712509421 513494097 185562763 32528961 384915356 656596371 478940575 876467676 725199841 708437459 344022139 527382636 569654142 783184165 118735724 121663391 216198889 808597615 71503793 556843318 621084364 170907118 723299840 506345862 353737863 877273521 502391554 364229627 305569453 414781469 591964115 169685905 428754307 542434919 207212163 17934681 203182980 459229981 288841879 140217082 158620127 724226206 52320648 880082733 572522231 253357981 200030530 740506688 435864290 592783266 92983463 157147284 550393835 826211720 125145098 119061280 96854801 456425984 316518836 304694763 231075973 657029645 532308067 601311893 114573360 197710727 641820102 487095503 388275754 659506072 792677122 201091806 672955716 310499649 957895472 391923228 350728575 857190870 673553884 152889719 199712403 514382206 57598344 118135793 611676265 49813428
268730919 134397214 626814881 924909513 988240290 662816681 617512461 997771103 831633495 737134543 90510132 63881967 566187924 399857634 170876112 475784772 103610400 716361927 513624400 572433662 552147635 788545144 322241623 25460497 800256122 252079748 399510843 33515331 763302804 936514698 875256199 114217393 662224279 38254273 747706745 608625738 744649739 421966963 805888645 10563410 323349229 664043134 620725200 247600097 457072430 375298514 370558645 342882402 751461682 355173365 751402308 185962260 846749010 828264322 31860414 536966796 283280986 564234405 294209050 792035377 284618763 397101985 993000068 872543935 351130 191490378 223189976 25188549 661555759 411050891 600959787 196755751 415301480 897592290 66323267 792472476 622396371 91767263 71745306 819438385 89406327 157508009 18840159 272483012 272843852 445488248 368969716 331068809 565659326 399827228 71071345 111991689 224730158 773551221 35930784 344567838 751718257 390591480 711609343 932339321 973501775 483322417 469265729 118466076 957067013 181973819 37173965 5942624 949133508 84940106 516300093 504319985 405707311 322172193 990257121 796332365 692335841 545825948 214055226 416624968 667342053 414251304 266104703 350996106 365592380 548832326 871449883 972526351 767223387 570553868 974988076 309465766 556123818 434876835 367774726 949423475 94308614 706079178 500049839 303802478 900352831 342793041 554425952 646009314 948969115 824572831 897617674 356025326 947895377 565595437 97269198 758957831 391009295 695980041 322179204 291614836 944127605 989869140 327551797 897128145 56903064 671066308 269396641 557266573 442265984 737249059 778003642 332559980 920047785 457254606 591178023 432518661 167587462 309752630 847289794 638398532 614741497 655441506 127129883 170159082 258085853 687543148 784074482 54114312 999703421 720047872 918458560 675097224 987784985 823718368 644473903 4872356 71743080 944389986 103210398 297894765 264555281 837351920 19155102 911270981 639050545 717267847 93773431 84167525 597082584 365064249 38015140 68862040 617060235 278323371 798387026 335070334 897532100 689293463 939835365 780636554 663378541 87016779 128999284 787825157 716378217 352433705 538875720 182350280 452793868 460295973 78213985 940385926 564534429 790039370 571179761 176462912 545699803 281383221 200882398 327250382 207927925 457547672 213123140 890464605 84053649 733621177 777056497 224704236 917759046 998780912 59249640 663791822 971727393 67897900 501515743 788946474 346456996 238317679 260486592 604304766 686895042 556156749 312221484 990902040 462420325 261571186 4961523 982750620 332099049 49844505 257138077 227653761 213821854 644836501 835797476 934325907 624929353 996049100 273603384 813661811 971965347 318528694 676572218 41892626 268645337 470266595 851103041 846088762 204202506 475067890 871418072 762873605 690984652 610624795 590211133 137298019 555552424 608392870 393364452 581399449 580564121 886592626 573437427 669948093 440725137 56239727 889763523 771798331 705041397 417945892 891243365 827290707 960546844 156536362 800628763 451649944 131918547 765587118 815344858 434372978 784095964 962414579 202776527 455543709 47214186 507899854 853222871 100479400 42518438 985154344 422793477 570688887 958135086 495171712 56611104 122065858 552595089 544066662 959283746 527824020 808836820 447973377 369271482 19543500 776036080 804271498 119014091 163818399 603134033 269876943 675768811 491709204 22101336 966279089 678720997 614943366 512829914 562656934 817417015 263714342 597501856 19449655 789178260 879146615 562337509 47869571 149742692 902816976 30354139 145425851 652941119 886830558 279215142 623693988 700924022 377295391 674127711 468036120 448168842 107818599 905095570 914305669 4838835 622294111 104555712 284852332 578587226 815934721 581000286 59628771 794090399 897905438 723984852 208777748 47705300 705368024 442294016 312289212 643214079 705826600 497659056 632627629 267543900 766889049 140318507 279725132 143054809 660031115 8073897 577189651 353668505 414294833 844071382 778066192 331642226 757488275 640429651 458975077 180013678 885753933 19317045 992639430 759470670 532085710 28617092 289770750 556559874 161981146 903815357 214211946 143200818 167155721 604353361 917124476 627999672 874874181 717239076 811183161 512359972 12721744 134530063 550639036 218854455 247852860 731180126 258494897 598468712 53802225 6812498 26201050 812576610 721133994 800905120 448418446 438067332 898786168 255850480 376338741 559866975 430599358 19967839 119937229 448551228 84614835 191949309 708986472 210993556 831357923 88526672 307409836 769925781 115028142 168419535 269867857 246568612 560231880 653590120 743141798 597807574 359728823 194573051 643192589 439601269 404026456 259084509 782813307 83523969 328632667 21581398 459059193 531841836 690209474 792446499 704657189 99115869 534648934 417820660 329400754 944192046 855930738 626949359 168242147 729025134 171104486 489258028 919854356 671502368 969118741 743593270 89921073 807359738 47451943 14645904 889048125 316794599 422764440 897356846 3097293 247420038 205813943 841760248 802137738 650214312 877122088 430440011 343869363 497442262 887681123 744715383 431905432 340465352 595621682 330877762 25174560 629121263 712001079 599684963 207803460 332283884 539052388 667331080 279599250 303377686 930414464 223596368 342508715 725305849 47487657 413906130 254212293 503770834 283731661 452955669 68883497 603784468 153586223 478865173 591267766 822867941 834000361 826333381 145120348 307635361 572491876 524445575 156052386 12989270 86530529 942705589 689445409 919978311 447230195 629646364 756746759 854493546 815122691 240007292 610343829 299240682 898106059 812577801 211620769 988252069 249541339 813850605 972966933 807918254 417961496 620889028 126951534 142671052 264425016 931005470 472787518 426415866 540230727 490813696 766591402 20815589 133509412 864776291 591878124 963253105 349209092 48703668 345561042 105925428 933333743 149807955 940265533 773784826 608666942 391228180 312364196 599042623 319706659 397186752 948640654 521246136 467821345 326188949 494131995 580460490 536930960 291563458 211443580 911409937 502102043 401020652 235746167 662321883 696725313 938628268 664410340 903034283 978434519 919073039 921936690 13461942 423950980 807738132 33293794 62940009 834003779 589368626 587487499 94351329 990434789 271094735 163241941 80740721 900608652 275402 917180158 138384416 236191794 825492722 536354648 113221160 637892896 422702220 11265096 672179320 683143031 6186961 378330697 973117747 13004202 657800813 23777127 521199663 600405250 952637186 241467333 363486071 611604505 864429475 248935959 538518986 977018719 820685913 676425769 943987481 771157401 264863137 963905878 55933709 745718364 593875180 673929489 444187006 512273046 494060830 190696288 135845629 768284934 460725520 66692955 948225867 375091903 517201423 208515506 202510304 857678761 588812378 987331877 595467877 576749312 890723751 186342153 500467514 65194963 979744670 467730378 818821105 472766342 663989853 258164067 340195793 842592848 796927218 497311207 787099220 815849406 956242404 166277116 714374569 303187758 415426475 892382555 941153074 137494101 595734323 148806994 226720263 78885306 487292510 199378753 908691314 513904952 331157119 518658848 394360689 565105280 661252831 406284280 225621816 635461013 890160443 887836773 206617516 699255630 842459204 154488603 9365480 413238231 619260446 126993246 596852668 414785328 475434721 171402632 810666025 838116781 90508571 522744711 929281510 958384756 40526413 131941724 792091614 73812482 364297577 737232797 22728624 143072422 840845147 288028659 128014382 630140677 118057853 321409437 368518622 493302420 762022944 277923308 301820796 846391841 203959562 432601797 654412406 239465035 561743859 3177762 401853294 761323525 23736583 657310097 395499196 692786455 674764647 216726195 224390890 737959581 687787943 371029438 902065462 620237190 741187154 855132412 558429203 908538134 967352418 171791434 912020904 949497700 973859784 942892442 898984527 659562461 26493930 35856241 32311575 842075071 857093151 984323433 121844291 432910495 894759989 908488368 649256905 63323364 259428588 521461384 865425876 631184457 770030201 89923781 931596099 763663967 140488964 318595154 899607080 727018760 756578602 17376172 587067977 704312573 124176507 32884069 676687778 984588362 61857789 256938146 750163168 314800845 340911783 15806366 298269672 921036474 186851303 136900133 16204878 833394457 469784093 462230554 270070238 997135942 578212637 576020465 328390423 975904881 157361841 853117749 576437675 395543068 105586965 701569283 227099905 93197472 595796345 247647886 828028595 240659112 492796547 839918489 52387088 895623347 715633866 83610368 624819099 671354262 59022684 490450735 784309130 165689080 5897273 372083369 734886984 504408533 105379541 180727938 426291187 891173116 308666522 913609958 874678238 972845969 593461092 2599312 478758161 974893451 753475075 347467347 445936324 383964215 887816380 998055829 959619304 418515123 380327881 418103503 901147294 613008500 253236180 40249102 381145277 147765185 410562688 107924853 782917200 463186485 263264480 311585209 6030614 79970113 664652286 116025507 300167169 829948583 926803286 999323282 377328567 388543744 57549656 772852214 948461332 173292087 16442857 699834838 18684838 891672076 957490402 584734283 422079536 573157523 305350800 750657795 943450407 286614194 628415538 74382271 124811576 40381606 954105471 864277717 404188608 558780542 177671709 688549806 657246034 629760670 753419819 990815561 82471477 883586622 669611704 238004919 202453219 593522665 110696265 198757789 689200780 395432447 952126295 957060789 808514961 269379379 988040398 747941965 790890505
